package tree

//给定一个二叉树，找出其最大深度。
//二叉树的深度为根节点到最远叶子节点的最长路径上的节点数

//深度优先搜索
func MaxDepth(root *Node) int {
	//返回递归条件
	if root == nil {
		return 0
	}
	//divide
	left := MaxDepth(root.Left)
	right := MaxDepth(root.Right)

	//conquer
	if left > right {
		return left + 1
	}
	return right + 1
}

//广度优先搜索
func MaxDephBFS(root *Node) int {
	if root == nil {
		return 0
	}
	queue := make([]*Node, 0)
	queue = append(queue, root)
	ans := 0
	for len(queue) > 0 {
		l := len(queue)
		for i := 0; i < l; i++ {
			node := queue[0]
			queue = queue[1:]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		ans++
	}
	return ans
}
